// =====================================================================================
// 
//       Filename:  ast.cpp
// 
//    Description:  Implémentation des arbres de structure abstraite 
// 
//        Version:  1.0
//        Created:  04/10/2009 23:15:17
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:  
// 
// =====================================================================================

#include	<cstdlib>
#include	<cmath>
#include	<cctype>
#include	<cstring>
#include	<string>
#include	"parser.h"
#include	"ast.h"

using namespace std;

namespace AST {
/********************************************/
/* IMPLEMENTATION DE LA CLASSE ASTEXCEPTION */
/********************************************/
const char* ASTException::what() const throw() {
	switch (code) {
		case BAD_TYPE:return ("Type de données incorrect : "+message).c_str();
		case SYNTAX_ERROR:return ("Erreur de syntaxe : "+message).c_str();
		case UNKNOWN_FUNCTION:return ("Fonction ou variable inconnue : "+message).c_str();
		default:return message.c_str();
	}
}

/*************************************/
/* IMPLEMENTATION DE LA CLASSE VALUE */
/*************************************/
Value::Value(double pval):_type(DOUBLE),_size(sizeof(double)) {
	_data=new char[_size];
	*((double*)(_data))=pval;
}

Value::Value(int pval):_type(INTEGER),_size(sizeof(int)) {
	_data=new char[_size];
	*((int*)(_data))=pval;
}

Value::Value(const string &pval):_type(STRING),_size(pval.size()) {
	_data=new char[_size];
	for (size_t i=0;i<_size;++i) _data[i]=pval[i];
}

Value::Value(bool pval):_type(BOOLEAN),_size(sizeof(bool)) {
	_data=new char[_size];
	*((bool*)(_data))=pval;
}

Value::Value(const Value& pval):_type(pval._type),_size(pval._size) {
	_data=new char[_size];
	memcpy(_data,pval._data,_size);
}

Value::~Value() {
	delete[] _data;
}

void Value::operator=(const Value &pval) {
	_type=pval._type;
	_size=pval._size;
	delete[] _data;
	_data=new char[_size];
	memcpy(_data,pval._data,_size);
}

double Value::get_double() const {
	if (_type!=DOUBLE && _type!=INTEGER) throw ASTException(ASTException::BAD_TYPE,"Double");
	if (_type==INTEGER) return (double)(*((int*)(_data)));
	else return *((double*)(_data));
}

int Value::get_integer() const {
	if (_type!=INTEGER) throw ASTException(ASTException::BAD_TYPE,"Integer");
	return *((int*)(_data));
}

string Value::get_string() const {
	if (_type!=STRING) throw ASTException(ASTException::BAD_TYPE,"String");
	return string(_data,_size);
}

bool Value::get_boolean() const {
	if (_type!=BOOLEAN) throw ASTException(ASTException::BAD_TYPE,"Boolean");
	return *((bool*)(_data));
}

/****************************************/
/* IMPLEMENTATION DE LA CLASSE FUNCTION */
/****************************************/
Function::Function(const string &pname,unsigned char pargs):_cur_child(0),_nbchildren(pargs),_name(pname) {
	_children=new SyntaxNode*[pargs];
}

Function::Function(const string &pname,SyntaxNode *arg):_cur_child(0),_nbchildren(1),_name(pname) {
	_children=new SyntaxNode*[1];
	_children[0]=arg;
}

Function::Function(const string &pname,SyntaxNode *arg1,SyntaxNode *arg2):_cur_child(0),_nbchildren(2),_name(pname) {
	_children=new SyntaxNode*[2];
	_children[0]=arg1;
	_children[1]=arg2;
}

Function::~Function() {
	for (unsigned char i=0;i<_nbchildren;++i) delete _children[i];
	delete[] _children;
}

Value Function::get_value(LookupFunction lookup,const void* data) const {
	Value vals[_nbchildren];
	for (unsigned char i=0;i<_nbchildren;++i) vals[i]=_children[i]->get_value(lookup,data);
	if (_nbchildren==0) {	// Variable
		if (lookup!=0) return lookup(_name,data);
	} else if (_nbchildren==1) {
		if (string_compare(_name,"sin")) return Value(sin(vals[0].get_double()));
		else if (string_compare(_name,"cos")) return Value(cos(vals[0].get_double()));
		else if (string_compare(_name,"tan")) return Value(tan(vals[0].get_double()));
		else if (string_compare(_name,"log")) return Value(log(vals[0].get_double()));
		else if (string_compare(_name,"exp")) return Value(exp(vals[0].get_double()));
		else if (string_compare(_name,"sqrt")) return Value(sqrt(vals[0].get_double()));
	} else if (_nbchildren==2) {
		if (string_compare(_name,"+")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()+vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()+vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()+vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()+vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()+vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"-")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()-vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()-vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()-vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()-vals[1].get_integer());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"*")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()*vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()*vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()*vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()*vals[1].get_integer());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"/")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()/vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()/vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()/vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()/vals[1].get_integer());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"^")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(pow(vals[0].get_double(),vals[1].get_double()));
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(pow(vals[0].get_double(),vals[1].get_integer()));
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(pow(double(vals[0].get_integer()),double(vals[1].get_integer())));
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"%")) {
			if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()%vals[1].get_integer());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"==")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()==vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()==vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()==vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()==vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()==vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"!=")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()!=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()!=vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()!=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()!=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()!=vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"<=")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()<=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()<=vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()<=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()<=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()<=vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,">=")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()>=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()>=vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()>=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()>=vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()>=vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,"<")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()<vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()<vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()<vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()<vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()<vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		} else if (string_compare(_name,">")) {
			if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()>vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_integer()>vals[1].get_integer());
			else if (vals[0].get_type(lookup,data)==DOUBLE && vals[1].get_type(lookup,data)==INTEGER) return Value(vals[0].get_double()>vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==INTEGER && vals[1].get_type(lookup,data)==DOUBLE) return Value(vals[0].get_double()>vals[1].get_double());
			else if (vals[0].get_type(lookup,data)==STRING && vals[1].get_type(lookup,data)==STRING) return Value(vals[0].get_string()>vals[1].get_string());
			else throw ASTException(ASTException::BAD_TYPE);
		}
	} else if (_nbchildren==3) {
		if (string_compare(_name,"if")) {
			if (vals[0].get_type(lookup,data)==BOOLEAN) {
				if (vals[0].get_boolean()) return vals[1]; else return vals[2];
			} else throw ASTException(ASTException::BAD_TYPE);
		}
	}
	throw ASTException(ASTException::UNKNOWN_FUNCTION,_name.c_str());
	return Value();
}

/**************************************************/
/* IMPLEMENTATION DES ARBRES DE SYNTAXE ABSTRAITE */
/**************************************************/
/**
 * \brief Tableau des opérateurs définissant la structure du langage
 *
 * Le tableau contient la liste des opérateurs binaires reconnus par la grammaire des expressions mathématiques. Le premier élément contient le nombre de catégories de priorités, représenté sous la forme d'une chaîne à zéro terminale, qui ne comprend qu'un caractère dont le code est le nombre de catégories. Les autres éléments contiennent en première position le nombre d'opérateurs appartenant à la catégorie de priorités correspondante représenté de la même façon que ci-dessus par une chaîne de caractères, puis la liste de ces opérateurs.
 */
static const char* operators[5][7]={{"\x04","","","","","",""},{"\x06","==","!=","<=",">=","<",">"},{"\x02","+","-","","","",""},{"\x03","*","/","%","","",""},{"\x01","^","","","","",""}};

/**
 * \brief Liste des caractères qui constituent un opérateur.
 *
 * Ce tableau est utilisé lors de la lecture d'un opérateur : dès qu'un caractère lu ne fait pas partie du tableau, le programme considère que l'opérateur a été lu en entier et recherche s'il connaît cet opérateur. Le tableau doit au minimum comprendre tous les caractères présents dans les différents éléments du tableau operators. Le premier élément du tableau contient le nombre d'éléments autres que lui-même.
 */
static const unsigned char operator_chars[11]={10,'+','-','*','/','^','%','=','<','>','!'};

const unsigned char MAX_ARGS=10;	//!< Nombre maximal d'arguments des fonctions dans les expressions mathématiques

/** \fn void ignore_blanks(const string &source,size_t &num) 
 * \brief Avance la position de lecture num jusqu'au premier caractère non blanc
 *
 * La fonction parcourt la chaîne de caractères source à partir de la position num pour trouver le premier caractère non blanc. Elle met à jour l'argument num avec la position de ce caractères. Si aucun caractère n'est trouvé, num prend la valeur de la longueur de la chaîne source.
 * \param source Chaîne de caractères à parcourir
 * \param num Début de la recherche. La valeur de num est mise à jour avec la position du premier caractère non blanc de la chaîne source au-delà de la position initiale.
 */
void ignore_blanks(const string &source,size_t &num) {
	while (num<source.size() && isspace(source[num])) num++;
}

/**
 * \fn bool in_array(const char *const *const array,const char* op)
 * \brief Vérifie si la chaîne de caractères appartient à un tableau de chaînes
 *
 * La fonction vérifie si la chaîne de caractères op appartient au tableau de chaînes de caractères array. Le tableau de chaînes de caractères doit contenir en première position la longueur de son contenu, à l'instar de la constante operators. La fonction est utilisée pour vérifier si un opérateur appartient à la grammaire définie par la variable operators.
 * \param array Tableau de chaînes de caractères à parcourir
 * \param op Chaîne de caractères à rechercher
 * \return Vrai si le tableau contient la chaîne de caractères, faux sinon
 */
bool in_array(const char *const *const array,const char* op) {
	for (unsigned char i=1;i<=array[0][0];++i) if (strcmp(array[i],op)==0) return true;
	return false;
}

/**
 * \fn bool in_array(const unsigned char *const array,unsigned char op)
 * \brief Vérifie si le caractère appartient à un tableau de caractères
 *
 * La fonction vérifie si le caractère op appartient au tableau de caractères array. Le tableau de caractères doit contenir en première position la longueur de son contenu, à l'instar de la constante operators_chars. La fonction est utilisée pour vérifier si un caractère particulier doit être lu comme la suite d'un opérateur en cours de lecture.
 * \param array Tableau de caractères à parcourir
 * \param op Caractère à rechercher
 * \return Vrai si le tableau contient le caractère, faux sinon
 */
bool in_array(const unsigned char *const array,unsigned char op) {
	for (unsigned char i=1;i<=array[0];++i) if (array[i]==op) return true;
	return false;
}

/**
 * \fn string get_operator(const string &source,size_t &num)
 * \brief Lit un opérateur depuis la chaîne de caractères à partir de la position num
 *
 * La fonction lit un opérateur depuis la chaîne de caractères en partant de la position num. L'opérateur est retourné sous forme d'une chaîne, et la position est mise à jour à la fin de la lecture. num prend ainsi la valeur de la position du premier caractère après l'opérateur. Les espaces et caractères blancs sont ignorés.
 * \param source Chaîne de caractères depuis laquelle l'opérateur doit être lu
 * \param num Position initiale de lecture. La variable est mise à jour avec la position du premier caractère après la lecture de l'opérateur.
 * \return Chaîne de caractères représentant l'opérateur
 */
string get_operator(const string &source,size_t &num) {
	if (num>=source.size()) throw ASTException(ASTException::SYNTAX_ERROR);
	ignore_blanks(source,num);
	size_t pos=num;
	while (num<source.size() && in_array(operator_chars,source[num])) num++;
	return source.substr(pos,num-pos);
}

SyntaxNode *get_E(const string &source,size_t &num,unsigned char priority) {
	if (num>=source.size()) throw ASTException(ASTException::SYNTAX_ERROR);
	ignore_blanks(source,num);
	SyntaxNode *res=0;	// Arbre syntaxique courant, mis à jour pendant la lecture de l'expression
	size_t pos;
	do {
		if (res==0) {
			if (priority==operators[0][0][0]) res=get_T(source,num); else res=get_E(source,num,priority+1);
		} else {
			string op=get_operator(source,num);
			SyntaxNode *cur=get_E(source,num,priority+1);
			res=new Function(op,res,cur);
		}
		ignore_blanks(source,num);
		pos=num;
		while (pos<source.size() && in_array(operator_chars,source[pos])) pos++;	// Recherche de la fin de l'opérateur
	} while (num<source.size() && in_array(operators[priority],source.substr(num,pos-num).c_str()));
	return res;
}

SyntaxNode *get_T(const string &source,size_t &num) {
	ignore_blanks(source,num);
	if (num>=source.size()) throw ASTException(ASTException::SYNTAX_ERROR);
	if (source[num]=='(') {	// T <- (E)
		num++;
		SyntaxNode *res=get_E(source,num,1);
		ignore_blanks(source,num);
		if (num>=source.size() || source[num]!=')') throw ASTException(ASTException::SYNTAX_ERROR);
		num++;
		return res;
	} else if ((source[num]>='a' && source[num]<='z') || (source[num]>='A' && source[num]<='Z') || source[num]=='_') { // T <- Function (Expression [,Expression [,...]])
		// Lecture de l'identifiant de la fonction
		size_t pos=num+1;
		char maj=toupper(source[pos]);
		while (pos<source.size() && ((maj>='A' && maj<='Z') || (maj>='0' && maj<='9') || maj=='_')) maj=toupper(source[++pos]);
		string id=source.substr(num,pos-num);
		num=pos;
		// Lecture des arguments
		unsigned char number_args=0;	// Nombre d'arguments lus
		SyntaxNode *args[MAX_ARGS];	// Tableau des arguments lus
		get_L(source,num,args,number_args);
		Function *res=new Function(id,number_args);
		for (size_t i=0;i<number_args;++i) res->add_child(args[i]);
		return res;
	} else {	// T <- constante
		if (source[num]=='"') {	// La constante est une chaîne de caractères
			size_t pos=num+1;
			while (pos<source.size() && (source[pos]!='"' || (pos<source.size()-1 && source[pos+1]=='"'))) pos++;
			if (pos>=source.size()) throw ASTException(ASTException::SYNTAX_ERROR);
			string val=source.substr(num+1,pos-num-1);
			num=pos+1;
			return new Value(val);
		} else if (source[num]=='-' || source[num]=='+' || isdigit(source[num])) {	// La constante est un nombre que l'on considère toujours flottant
			size_t pos=num+1;
			while (pos<source.size() && isdigit(source[pos])) pos++;
		   	if (source[pos]=='.') {
				pos++;
				while (pos<source.size() && isdigit(source[pos])) pos++;
			}
			if (source[pos]=='e' || source[pos]=='E') {
				pos++;
				if (source[pos]=='+' || source[pos]=='-') pos++;
				while (pos<source.size() && isdigit(source[pos])) pos++;
			}
			istringstream iss(source.substr(num,pos-num));
			num=pos;
			double val;
			iss >> val;
			return new Value(val);
		} else throw ASTException(ASTException::SYNTAX_ERROR);
	}
}

void get_L(const string &source,size_t &num,SyntaxNode **args,unsigned char &nbargs) {
	ignore_blanks(source,num);
	if (num>=source.size() || source[num]!='(') {	// Cas où la liste ne contient aucune expression
		nbargs=0;
		args=0;
		return;
	}
	// Cas général : la liste contient une ou plusieurs expressions et est délimitée par des parenthèses
	do {
		num++;
		args[nbargs++]=get_E(source,num);
		ignore_blanks(source,num);
		if (num>=source.size() || (source[num]!=',' && source[num]!=')')) throw ASTException(ASTException::SYNTAX_ERROR);
	} while (nbargs<MAX_ARGS && num<source.size() && source[num]!=')');
	if (nbargs==MAX_ARGS) while (num<source.size() && source[num]!=')') num++;
	if (num>=source.size()) throw ASTException(ASTException::SYNTAX_ERROR);
	num++;
}
}
